import java.util.Stack;

public class Floyd {
	protected int b[][] = null;

	protected int indexSta;
	protected int indexEnd;
	protected Stack<Integer> arrange = new Stack<Integer>();
	public Boolean shortesPath(Graph g, Vertex sta, Vertex end) {
		int n = g.vertices.size();
		int a[][] = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				a[i][j] = g.dismat[i][j];
				if(a[i][j]==-1)
					a[i][j]=10000;
			}
		}
		
		
		int[][] b = new int[n][n];
		// initial matrix vertex adjacency
		//System.out.println(n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][j] == 0 || a[i][j] == 10000)
					b[i][j] = 0;
				else {
					b[i][j] = i + 1;
				}
			}
		}
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (a[i][j] > a[i][k] + a[k][j]) {
						a[i][j] = a[i][k] + a[k][j];
						b[i][j] = b[k][j];
					}
				}

			}

		}
		System.out.print("\n");
		System.out.print("\n");
		System.out.println("Matrix vertices");
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {

				System.out.print(b[i][j]);
				System.out.print("\t");

			}
			System.out.print("\n");
		}

		System.out.println("start" + sta.value + "(" + sta.x + "," + sta.y
				+ ")");
		System.out.println("end" + end.value + "(" + end.x + "," + end.y + ")");
		// get index in array of vertices
		for (Vertex u : g.vertices) {
			if (u.equals(sta)) {

				indexSta = g.vertices.indexOf(u) + 1;

			}
			if (u.equals(end)) {
				indexEnd = g.vertices.indexOf(u) + 1;
			}
		}
		System.out.println(indexSta);

		System.out.println(indexEnd);
		int t = indexEnd;
		System.out.println(t + "," + indexEnd);
		
		// get path
		arrange.push(t);
		try {
			while (t != indexSta) {
				t = b[indexSta - 1][t - 1];
				arrange.push(t);

			}
		} catch (Exception e) {
			// TODO: handle exception
			//System.out.println("not path from start to end ");
			return false;
		}
		
//		if(t!=indexSta)
//		{
//			// not path from start to end 
//			return false;
//		}
//		else 
			return true;
//		String str = "";
//		int sum = 0;
//		while (!arrange.isEmpty()) {
//			int i, j;
//			i = arrange.pop();
//			j = arrange.peek();
//			str += g.vertices.get(i-1).value + "-";
//			sum += g.dismat[i-1][j-1];
//			if (arrange.size() == 1) {
//				str += g.vertices.get(arrange.pop()-1).value + "\n";
//			}
//		}		
	}
	

}
